// https://www.acwing.com/problem/content/2/

#include <iostream>
#include <vector>

using namespace std;

/**
 * 解决0-1背包问题（每个物品不可重复选择）
 *
 * 状态转移方程：f[j] 表示容量为 j 时的最大价值
 *
 *  f[j] = max(f[j], f[j-weights[i]] + values[i])
 *
 * @param w 背包的最大容量
 * @param weights 物品的重量数组
 * @param values 物品的价值数组
 * @return 返回一个整数，即在容量不超过 w 的情况下，能获得的最大价值
 *
 * 为什么一维情况下枚举背包容量需要逆序？在二维情况下，状态f[i][j]是由上一轮 i - 1 的状态得来的，f[i][j]与f[i - 1][j]是独立的。
 * 而优化到一维后，如果我们还是正序，则有f[较小体积]更新到f[较大体积]，则有可能本应该用第 i-1 轮的状态却用的是第i轮的状态。
 */
int knapsack(const int w, const vector<int>& weights, const vector<int>& values) {
    // f[i][t] 表示前 i 个物品，容量为 t 时的最大价值
    const int n = weights.size()-1;
    vector<int> dp(w+1);
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j=w; j >= weights[i]; j--) {
            dp[j] = max(dp[j], dp[j-weights[i]] + values[i]);
        }
    }

    return dp[w];
}

int main() {
    int n, w;
    cin>>n>>w;
    vector<int> weights(n+1), values(n+1);

    for (int i = 1; i <= n; i++) {
        cin>>weights[i]>>values[i];
    }
    cout<<knapsack(w, weights, values)<<endl;

    return 0;
}
/*
4 5
1 2
2 4
3 4
4 5

8
*/